//https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=23274&ru=%2Fpractice%2F9f3231a991af4f55b95579b44b7a01ba&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
//思想：二分解决；重要！！！

#include <iostream>
#include <vector>
using namespace std;

class Solution{
  public:
    //二分查找
   int GetNumberOfK(vector<int>& data, int k) {
        // 找到左边界
       int first = binarySearch(data,k);
        // 找到右边界（注意：k+1）
       int last = binarySearch(data,k+1);
        // 若超出数组范围，则证明目标值出现的次数为0，否则，右边界减去左边界即能统计出目标出现的次数
        return (first==data.size() || data[first]!=k)?0:last-first;
    }
 
    int binarySearch(vector<int>& data, int k){
        // 左右边界
        int l = 0, r = data.size();
        while(l < r){
            // 二分求中点
            int m = l+(r-l)/2;
            if(data[m] >= k)
                r = m;
            else
                l = m+1;
        }
        // 返回左边界
        return l;
    }
};